#include <vector>
#include <algorithm>
using namespace std;
/*
 * @lc app=leetcode.cn id=134 lang=cpp
 *
 * [134] 加油站
 */

// @lc code=start
class Solution {
public:
    // 暴力法, 超时
    // int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    //     for (int i = 0; i < gas.size(); i++) {
    //         int j = i, storage = 0;
    //         do {
    //             storage += (gas[j] - cost[j]);
    //             if (storage < 0) break;
    //             j = (j + 1) % gas.size();
    //         } while (j != i);
    //         if (storage >= 0) return i;
    //     }
    //     return -1;
    // }

    // 从折线图的角度思考
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int minv = INT_MAX, mini = 0, sum = 0;
        for (int i = 0; i < gas.size(); i++) {
            sum += gas[i] - cost[i];
            if (sum < minv) {
                minv = sum; mini = i;
            }
        }
        return sum < 0 ? -1 : (mini + 1) % gas.size();
    }

    // 解法2: x -> y如果不可行, 那么 i in [x, y)都不可行
    
};
// @lc code=end

